#pragma once

#include<vector>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) :
		val(x), left(left),
		right(right) {}
};


class Solution {
public:
	TreeNode* _buildTree(size_t begini, size_t endi,
		const vector<int>& preorder, size_t& pre_i,
		const vector<int>& inorder)
	{
		if (begini >= endi)
		{
			return nullptr;
		}


		for (size_t rooti = begini; rooti < endi; ++rooti)
		{
			if (preorder[pre_i] == inorder[rooti])
			{
				TreeNode* root = new TreeNode(preorder[pre_i++]);
				//[begini,rooti) rooti [rooti+1,endi)
				root->left = _buildTree(begini, rooti, preorder, pre_i, inorder);
				root->right = _buildTree(rooti + 1, endi, preorder, pre_i, inorder);

				return root;
			}
		}

	}

	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
	{
		size_t pre_i = 0;
		return _buildTree(0, inorder.size(), preorder, pre_i, inorder);
	}
};


class Solution2 {
public:
	TreeNode* _buidTree(const vector<int>& inorder, const vector<int>& postorder
		, size_t begini, size_t endi
		, size_t& posti)
	{
		if (begini >= endi)
			return nullptr;

		size_t post_backi = postorder.size() - 1;
		for (size_t rooti = begini; rooti < endi; ++rooti)
		{
			if (postorder[post_backi - posti] == inorder[rooti])
			{
				TreeNode* root = new TreeNode(inorder[rooti]);
				++posti;
				root->left = _buidTree(inorder, postorder, begini, rooti, posti);
				root->right = _buidTree(inorder, postorder, rooti + 1, endi, posti);
			}
		}
		return nullptr;
	}

	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		size_t tmp = 0;

		return _buidTree(inorder, postorder, 0, inorder.size(), tmp);

	}
};

void test()
{
	vector<int> preorder = { 3,9,20,15,7 };
	vector<int> inorder = { 9,3,15,20,7 };
	Solution().buildTree(preorder, inorder);
}

void test2()
{
	vector<int> preorder = { -1 };
	vector<int> inorder = { -1 };
	Solution2().buildTree(preorder, inorder);
}